import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        int[] arr = new int[]{2,1,2,3,2};
        directSelectSort(arr);
        // 打印测试结构
        System.out.println(Arrays.toString(arr));
    }

    public static void directSelectSort(int[] arr) {
        /**
         * 直接选择排序
         *  算法思想：
         *      1，每次找到数组待排序区间中的最大值和最小值
         *          问题：最大值和最小值是同一个元素（待排序数组中仅有一个元素 或者 均是相同元素）
         *      2，交换边界处的元素，边界步进，直至待排序区间为零
         *  特殊情况讨论：
         *      当一个区间中最大值与最小值相同，此时就已经无需再排序了，因为已经有序！*/
        // 1 预处理
        int n = arr.length;

        // 2 直接选择排序
        int left = -1;
        int right = n;
        while(left + 1 < right) {
            // -1 存储最值
            int minValue = Integer.MAX_VALUE;
            int maxValue = Integer.MIN_VALUE;
            int minIndex = -1;
            int maxIndex = -1;

            // -2 在当前循环中找到最值
            for(int i = left + 1; i < right; i++) {
                if(arr[i] > maxValue) {
                    maxValue = arr[i];
                    maxIndex = i;
                }
                if(arr[i] < minValue) {
                    minValue = arr[i];
                    minIndex = i;
                }
            }

            // -3 判断元素
            if(minValue == maxValue) {
                // -最大值和最小值相等，此时已经无需再排序
                break;
            } else {
                /**
                 * 此处需要注意：
                 *  我们第一次会交换 ++left 和 minIndex，第二次会交换--right 和 maxIndex
                 *  若是maxIndex = ++left，那么此轮就会无效交换，故需要判定，若是，则将maxIndex指向正确位置*/
                swap(arr, ++left, minIndex);
                if(left == maxIndex) {
                    maxIndex = minIndex;
                }
                swap(arr, --right, maxIndex);
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        /**
         * 交换两个元素的位置*/
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
